<!DOCTYPE html>
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <meta http-equiv="X-UA-Compatible" content="ie=edge">
  <title>Document</title>
</head>
<body>
  
</body>
<script>
  let arr = [5, 2, 4, 1, 6, 3]
  // 选择排序
  function selectSort(arr) {
    for (let i = 1; i < arr.length; i++) {
      for (let j = i; j < arr.length; j++) {
        if (arr[i-1] > arr[j]) {
          [arr[i-1], arr[j]] = [arr[j], arr[i-1]]
        }
      }
    }
    return arr
  }
  // 插入排序
  function insertSort(arr) {
    for (let i = 0; i < arr.length-1; i++) {
      for (let j = i; j >= 0; j--) {
        if (arr[j+1] < arr[j]) {
          [arr[j+1], arr[j]] = [arr[j], arr[j+1]]
        }
        console.log(arr);
      }
      console.log(' ');
    }
    return arr
  }
  // 冒泡排序
  function bubbleSort(arr) {
    for (let i = arr.length - 1; i > 0; i--) {
      for (let j = 0; j < i; j++) {
        if (arr[j+1] < arr[j]) {
          [arr[j+1], arr[j]] = [arr[j], arr[j+1]]
        }
      }
    }
    return arr
  }  
  // 希尔排序
  function shellSort(arr) {
    for (let gap = arr.length/2 ; gap> 0; gap = Math.floor(gap/2)) {
      for (let i = gap; i < arr.length; i++) {
        for (let j = i - gap; j >= 0; j -= gap) {
          if (arr[j + gap] < arr[j]) {
            [arr[j + gap], arr[j]] = [arr[j], arr[j + gap]]
          }
        }
      }      
    }
    return arr;
  }
  // 堆排序
  function heapSort(arr) {
    let lastNodeIndex = arr.length / 2 - 1 | 0
    while (lastNodeIndex > -1) {
      shiftDown(arr, lastNodeIndex--, arr.length)
    }
    for (let i = arr.length - 1; i > 0; i--) {
      shiftDown(arr, 0, i);
      [arr[0], arr[i]] = [arr[i], arr[0]]
    }
    return arr
    function shiftDown(arr, i, len) {
      let j = 2 * i + 1
      if (j + 1 < len && arr[j] < arr[j + 1]) {
        j++
      }
      if (j < len && arr[i] < arr[j]) {
        [arr[i], arr[j]] = [arr[j], arr[i]]
        shiftDown(arr, j, len)
      }
    }
  }
  // 归并排序
  function mergeSort(arr) {
    if (arr.length === 1) {
      return arr
    }
    let mid = arr.length / 2 | 0
    return merge(mergeSort(arr.slice(0, mid)), mergeSort(arr.slice(mid)))
    function merge(left, right) {
      let result = []
      while (left.length && right.length) {
        if (left[0] < right[0]) {
          result.push(left.shift())
        } else {
          result.push(right.shift())
        }
      }
      return result.concat(left, right)
    }
  }

  /**
   *     A
   *   B   C
   *  D E F G
   */
  let tree = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F', 'G']
  }
  // 深度优先搜索
  function dfs(tree, node, list=[]) {
    list.push(node)
    let child = tree[node]
    child && child.forEach(e => dfs(tree, e, list))
    return list
  }
  // console.log(dfs(tree, 'A'));

  // 广度优先搜索
  function bfs(tree, node, list=[]) {
    let stack = [node]
    while (stack.length) {
      let child = stack.shift()
      list.push(child)
      tree[child] && stack.push(...tree[child])
    }
    return list
  }
  // console.log(bfs(tree, 'A'));
  
  // 节流
  // 如果一个函数持续地触发，那么在固定的事件执行一次
  function throttle(fn, ms=1000) {
    let cd = true
    return function() {
      if (!cd) return
      cd = false
      setTimeout(_=> {
        fn.apply(this, arguments)
        cd = true
      }, ms)
    }
  }
  // 防抖
  // 如果一个函数持续地触发，那么只在它结束后过一段时间只执行一次
  function debounce(fn, ms=1000) {
    let timer = null
    return function() {
      clearTimeout(timer)
      timer = setTimeout(_=> {
        fn.apply(this, arguments)
      }, ms)
    }
  }
  function sayHi(name) {
    console.log(name);
  }
  // let fn = debounce(sayHi)
  // window.onmousemove = function() {
  //   fn('debounce: hans')
  // }
  // let fn2 = throttle(sayHi)
  // setInterval(_=> {
  //   fn2('throttle: hans')
  // }, 10)

  // 对象深拷贝
  // JSON实现简单的对象深拷贝，不能拷贝函数、undefined和Symbol
  function JSONClone(obj) {
    return JSON.parse(JSON.stringify(obj))
  }
  function simpleClone(obj) {
    let copy = Array.isArray(obj) ? [] : {}
    for (const key in obj) {
      const elt = obj[key];
      copy[key] = (typeof elt === 'object' && elt !== 'null')
        ? simpleClone(elt)
        : elt
    }
    return copy
  }

  // let syb = Symbol('obj')
  // let array = [1, 2, 3, 4, 5]
  // let bar = {
  //   name: 'bar',
  //   baz: {
  //     name: 'baz',
  //     aChild: null //待会让它指向obj.foo
  //   }
  // }
  // let circleObj = {
  //   foo: {
  //     name: function() {
  //       console.log(1)
  //     },
  //     syb: syb,
  //     un: undefined,
  //     num: NaN,
  //     arr: array,
  //     bar: bar
  //   }
  // }
  // bar.baz.aChild = circleObj.foo
  // console.log(simpleClone(circleObj));
  
  // 实现一个newX函数，具有new的功能
  // function newX(Fn, ...args) {
  //   let obj = Object.create(Fn.prototype)
  //   let ret = Fn.apply(obj, args)
  //   return ret instanceof Object ? ret : obj
  // }
  // function Ball(radius=10, color='red') {
  //   this.randius = radius
  //   this.color = color
  //   this.move = function() {
  //     console.log('move');
  //   }
  // }
  // let ball = new Ball(20)
  // let ball2 = newX(Ball, 100)
  // console.log(ball, ball2);
  
  // 完善typeof
  // function getType(val) {
  //   let cfg = {
  //     '[object Object]': 'object',
  //     '[object Array]': 'array',
  //     '[object Number]': 'object number',
  //     '[object Boolean]': 'object boolean',
  //     '[object String]': 'object string',
  //     '[object Null]': 'null',
  //   }
  //   let type = typeof val
  //   let toString = e => Object.prototype.toString.call(e)
  //   return type === 'object' ? cfg[toString(val)] : type
  // }

  // 给定一个整数数组 nums 和一个目标值 target
  // 请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
  // function twoSum(nums, target) {
  //   let map = new Map()
  //   for (let i = nums.length - 1; i >= 0; i--) {
  //     let val = map.get(target - nums[i])
  //     if (val) {
  //       return [i, val]
  //     }
  //     map.set(nums[i], i)
  //   }
  //   return null
  // }
  // let nums = [2, 7, 11, 15], target = 9
  // console.log(twoSum(nums, target));
  
  // var reverse = function(x) {
  //     let i = 0, val = 0
  //     while(x) {
  //         let a = x % 10
  //         x = x / 10 | 0
  //         val = val * 10 + a
  //     }
  //     return val
  // };
  // console.log(reverse(1534236469));
  
  //判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数
  // function isPalindrome(num) {
  //   if (num < 0) return false
  //   let i = 0, val = 0, x = num
  //   while (x) {
  //     let a = x % 10
  //     x = x / 10 | 0
  //     val = val * 10 + a
  //   }
  //   return num === val
  // }
  // console.log(isPalindrome(123))
  // console.log(isPalindrome(121))

  // 给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序
  // 输入: "Let's take LeetCode contest"
  // 输出: "s'teL ekat edoCteeL tsetnoc"

  // function reverseWords(s) {
  //   return s.split(' ').reduce((s, e) => s += e.split('').reverse().join('') + ' ', '').trim()
  // }
  // console.log(reverseWords("Let's take LeetCode contest"));
  

</script>
</html>